#pragma once

#include <iostream>
#include "bstree.hpp"

template<class K, class V>
class bs_tree_r
{
public:
    typedef bst_node<K, V> node;

public:

    bool find(const K& key)
    {
        return _find(_root, key);
    }

    bool _find(node* root, const K& key)
    {
        if (!root)
        {
            return false;
        }

        if (root->_key < key)
        {
            return _find(root->_right, key);
        }
        else if (root->_key > key)
        {
            return _find(root->_left, key);
        }
        else
        {
            return true;
        }
    }

    bool insert(const K& key, const V& val)
    {
        return _insert(_root, key, val);
    }

    bool _insert(node*& root, const K& key, const V& val)
    {
        if (!root)
        {
            root = new node(key, val);
            return true;
        }

        if (root->_key < key)
        {
            return _insert(root->_right, key, val);
        }
        else if (root->_key > key)
        {
            return _insert(root->_left, key, val);
        }
        else
        {
            return false;
        }
    }

    bool erase(const K& key)
    {
        return _erase(_root, key);
    }

    bool _erase(node*& root, const K& key)
    {
        if (!root)
        {
            return false;
        }

        if (root->_key < key)
        {
            return _erase(root->_right, key);
        }
        else if (root->_key > key)
        {
            return _erase(root->_left, key);
        }
        else
        {
            node* del = root;

            if (!root->_left)
            {
                root = root->_right;
            }
            else if (!root->_right)
            {
                root = root->_left;
            }
            else
            {
                node* min = root->_right;

                while (min->_left)
                {
                    min = min->_left;
                }
                
                root->_key = min->_key;
                return _erase(root->_right, min->_key); // mast erase in the big son tree
            }

            delete del;
            return true;
        }

    }

    void inorder()
    {
        _inorder(_root);
        cout << endl;
    }

    void _inorder(node* root)
    {
        if (!root)
            return;

        _inorder(root->_left);
        cout << root->_key << " ";
        _inorder(root->_right);
    }

private:
    node* _root = nullptr;
};
